# 给定一个单向链表L:(L0->L1-> … -> Ln-1-> Ln)，写出一个程序重新排序它，使它最后变成(Ln-> L0-> Ln-1-> L1-> Ln-2-> L2-> …)。
# 例如给定(1-> 2-> 3-> 4),重新排序成(4-> 1-> 3-> 2)

class Node:
    def __init__(self, x):
        self.x = x
        self.next = None


def reorder(head: Node):
    n1 = head
    n2 = head
    while n2.next and n2.next.next:
        n1 = n1.next
        n2 = n2.next.next
    n2 = n1.next
    n1.next = None
    while n2:
        n3 = n2.next
        n2.next = n1
        n1 = n2
        n2 = n3
    n2 = n1
    while head.next:
        n3 = n2.next
        n4 = head.next
        n2.next = head
        head.next = n3
        head = n4
        n2 = n3
    return n1


if __name__ == "__main__":
    head = Node(1)
    head.next = Node(2)
    head.next.next = Node(3)
    head.next.next.next = Node(4)
    res = reorder(head)
    while res:
        print(res.x)
        res = res.next